package com.lx.algorithm.recursion.class19;

import com.lx.algorithm.Utils;

import java.util.Random;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-18 15:21:10
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-18     张李鑫                     1.0         1.0 Version
 */
public class Knapsack {
    /**
     * 背包问题:
     * 给定两个长度都为N的数组weights和values，
     * weights[i]和values[i]分别代表 i号物品的重量和价值。
     * 给定一个正数bag，表示一个载重bag的袋子，
     * 你装的物品不能超过这个重量。
     * 返回你能装下最多的价值是多少?
     */

    public static int bag(int[] weights, int[] values, int bag) {
        if (weights == null || bag == 0 || values == null || values.length == 0 || weights.length != values.length) {
            return 0;
        }
        return process(weights, values, bag, 0);
    }

    private static int process(int[] weights, int[] values, int bag, int i) {
        if (bag < 0) {
            return Integer.MAX_VALUE;
        }
        if (i == weights.length) {
            return 0;
        }
        int val = 0;
        int process = process(weights, values, bag - weights[i], i + 1);
        if (process != Integer.MAX_VALUE) {
            val = values[i] + process;
        }
        return Math.max(val, process(weights, values, bag, i + 1));
    }


    public static int dp(int[] weights, int[] values, int bag) {
        if (weights == null || bag == 0 || values == null || values.length == 0 || weights.length != values.length) {
            return 0;
        }
        int[][] dp = new int[weights.length + 1][bag + 1];

        for (int i = weights.length - 1; i >= 0; i--) {
            for (int j = 0; j < dp[i].length; j++) {
                int max = dp[i + 1][j];
                if (j - weights[i] >= 0) {
                    max = Math.max(dp[i + 1][j - weights[i]] + values[i], max);
                }
                dp[i][j] = max;
            }
        }
        return dp[0][bag];
    }


    public static int dpII(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }
        int N = w.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= bag; rest++) {
                int p1 = dp[index + 1][rest];
                int p2 = 0;
                int next = rest - w[index] < 0 ? -1 : dp[index + 1][rest - w[index]];
                if (next != -1) {
                    p2 = v[index] + next;
                }
                dp[index][rest] = Math.max(p1, p2);
            }
        }
        return dp[0][bag];
    }

    public static void main(String[] args) {
        Random random = new Random();
        for (int i = 0; i < 10000; i++) {
            int[] weights = Utils.generateRandomMatrix(20);
            int[] values =  Utils.generateRandomMatrix(20);
            int bag = random.nextInt(100);
            if (dp(weights, values, bag) != dpII(weights, values, bag)) {
                System.out.println("error");
                Utils.printMatrix(weights);
                Utils.printMatrix(values);
                break;
            }
        }
    }
}
